Shareware Grab Bag/Shareware Grab Bag.iso/011/lz.arc/LZCOMP.ASM

Assembly Source File | 1986-07-01 | 7.1 KB | 288 lines

    title    lzcomp - file compressor using limpel-ziv algorithm

;Tom Pfau
;Digital Equipment Corporation
;Parsippany, NJ

;Constants
clear        equ    256        ;Clear code
eof        equ    257        ;End of file marker
first_free    equ    258        ;First free code
maxmax        equ    4096        ;Max code + 1

    include macros.mlb

;Hash table entry
hash_rec    struc
first    dw    ?            ; First entry with this value
next    dw    ?            ; Next entry along chain
char    db    ?            ; Suffix char
hash_rec    ends

;Declare Segments
code    segment byte public 'code'
code    ends
stack    segment word stack 'data'
    dw    128 dup (?)
stack    ends
data    segment word public 'data'
data    ends
memory    segment para public 'memory'
hash    label    hash_rec
memory    ends

;Start writing code
code    segment
    assume    cs:code,ds:data,es:data,ss:stack

start    proc    far
    mov    bx,seg hash        ;End of program
    mov    ax,ds            ;Start of program
    sub    bx,ax            ;Program size
    inc    bx            ;Make sure
    setmem    bx            ;Set our size
    mov    bx,data            ;Set up data segment addressability
    mov    es,bx
    mov    ds,bx
    print    input_prompt        ;Get input file name
    input    input_file
    print    crlf
    print    output_prompt        ;And output
    input    output_file
    print    crlf
    mov    al,input_file+1        ;Terminate file names with nulls
    xor    ah,ah
    mov    si,ax
    mov    input_file+2[si],0
    mov    al,output_file+1
    mov    si,ax
    mov    output_file+2[si],0
    hopen    input_file+2,0
    mov    input_handle,ax
    hcreat    output_file+2,0
    mov    output_handle,ax
    call    compress        ;Compress file
    hclose    input_handle        ;Close in and out
    hclose    output_handle
    exit                ;Done
start    endp

data    segment
input_prompt    db    'Input file: $'
output_prompt    db    'Output file: $'
input_file    db    80,0,80 dup (?)
output_file    db    80,0,80 dup (?)
crlf        db    13,10,'$'
input_handle    dw    ?
output_handle    dw    ?
data    ends

compress    proc    near
    malloc    1280            ;Allocate space for hash table
    mov    hash_seg,ax        ;Save segment address
l1:    call    init_table        ;Initialize the table and some vars
    mov    ax,clear        ;Write a clear code
    call    write_code
    call    read_char        ;Read first char
l4:    xor    ah,ah            ;Turn char into code
l4a:    mov    prefix_code,ax        ;Set prefix code
    call    read_char        ;Read next char
    jc    l17            ;Carry means eof
    mov    k,al            ;Save char in k
    mov    bx,prefix_code        ;Get prefix code
    call    lookup_code        ;See if this pair in table
    jnc    l4a            ;nc means yes, new code in ax
    call    add_code        ;Add pair to table
    push    bx            ;Save new code
    mov    ax,prefix_code        ;Write old prefix code
    call    write_code
    pop    bx
    mov    al,k            ;Get last char
    cmp    bx,max_code        ;Exceed code size?
    jl    l4            ;less means no
    cmp    nbits,12        ;Currently less than 12 bits?
    jl    l14            ;yes
    mov    ax,clear        ;Write a clear code
    call    write_code
    call    init_table        ;Reinit table
    mov    al,k            ;get last char
    jmp    l4            ;Start over
l14:    inc    nbits            ;Increase number of bits
    shl    max_code,1        ;Double max code size
    jmp    l4            ;Get next char
l17:    mov    ax,prefix_code        ;Write last code
    call    write_code
    mov    ax,eof            ;Write eof code
    call    write_code
    mov    ax,bit_offset        ;Make sure buffer is flushed to file
    cmp    ax,0
    je    l18
    mov    cx,8            ;convert bits to bytes
    xor    dx,dx
    div    cx
    or    dx,dx            ;If extra bits, make sure they get
    je    l17a            ;written
    inc    ax
l17a:    call    flush
l18:    ret
compress    endp

data    segment
hash_seg    dw    ?
prefix_code    dw    ?
free_code    dw    ?
max_code    dw    ?
nbits        dw    ?
k        db    ?
data    ends

init_table    proc    near
    mov    nbits,9            ;Set code size to 9
    mov    max_code,512        ;Set max code to 512
    push    es            ;Save seg reg
    mov    es,hash_seg        ;Address hash table
    mov    ax,-1            ;Unused flag
    mov    cx,640            ;Clear first 256 entries
    mov    di,offset hash        ;Point to first entry
rep    stosw                ;Clear it out
    pop    es            ;Restore seg reg
    mov    free_code,first_free    ;Set next code to use
    ret                ;done
init_table    endp

write_code    proc    near
    push    ax            ;Save code
    mov    ax,bit_offset        ;Get bit offset
    mov    cx,nbits        ;Adjust bit offset by code size
    add    bit_offset,cx
    mov    cx,8            ;Convert bit offset to byte offset
    xor    dx,dx
    div    cx
    cmp    ax,1020            ;Approaching end of buffer?
    jl    wc1            ;less means no
    call    flush            ;Write the buffer
    push    dx            ;dx contains offset within byte
    add    dx,nbits        ;adjust by code size
    mov    bit_offset,dx        ;new bit offset
    pop    dx            ;restore dx
    add    ax,offset output_data    ;Point to last byte
    mov    si,ax            ;put in si
    mov    al,byte ptr [si]    ;move byte to first position
    mov    output_data,al
    xor    ax,ax            ;Byte offset of zero
wc1:    add    ax,offset output_data    ;Point into buffer
    mov    di,ax            ;Destination
    pop    ax            ;Restore code
    mov    cx,dx            ;offset within byte
    xor    dx,dx            ;dx will catch bits rotated out
    jcxz    wc3            ;If offset in byte is zero, skip shift
wc2:    shl    ax,1            ;Rotate code
    rcl    dx,1
    loop    wc2
    or    al,byte ptr [di]    ;Grab bits currently in buffer
wc3:    stosw                ;Save data
    mov    al,dl            ;Grab extra bits
    stosb                ;and save
    ret
write_code    endp

data    segment
bit_offset    dw    ?
output_data    db    1024 dup (?)
data    ends

flush        proc    near
    push    ax            ;Save all registers
    push    bx            ;AX contains number of bytes to write
    push    cx
    push    dx
    hwrite    output_handle,output_data,ax    ;write output file
    pop    dx
    pop    cx
    pop    bx
    pop    ax
    ret
flush        endp

read_char    proc    near
    mov    di,input_offset        ;Anything left in buffer?
    cmp    di,input_size
    jl    rd1            ;less means yes
    hread    input_handle,input_data,1024    ;Read next chunk of input
    cmp    ax,0            ;Anything left?
    je    rd2            ;equal means no, finished
    mov    input_size,ax        ;Save bytes read
    mov    input_offset,0        ;Point to beginning of buffer
    mov    di,0
rd1:    lea    si,input_data[di]    ;Point at character
    lodsb                ;Read it in
    inc    input_offset        ;Adjust pointer
    clc                ;Success
    ret
rd2:    stc                ;Nothing left
    ret
read_char    endp

data    segment
input_data    db    1024 dup (?)
input_offset    dw    0
input_size    dw    0
data    ends

lookup_code    proc    near
    push    ds            ;Save seg reg
    mov    ds,hash_seg        ;point to hash table
    call    index            ;convert code to address
    mov    di,0            ;flag
    cmp    [si].first,-1        ;Has this code been used?
    je    gc4            ;equal means no
    inc    di            ;set flag
    mov    bx,[si].first        ;Get first entry
gc2:    call    index            ;convert code to address
    cmp    [si].char,al        ;is char the same?
    jne    gc3            ;ne means no
    clc                ;success
    mov    ax,bx            ;put found code in ax
    pop    ds            ;restore seg reg
    ret                ;done
gc3:    cmp    [si].next,-1        ;More left with this prefix?
    je    gc4            ;equal means no
    mov    bx,[si].next        ;get next code
    jmp    gc2            ;try again
gc4:    stc                ;not found
    pop    ds            ;restore seg reg
    ret                ;done
lookup_code    endp

index        proc    near
    mov    si,bx            ;si = bx * 5 (5 byte hash entries)
    shl    si,1            ;si = bx * 2 * 2 + bx
    shl    si,1
    add    si,bx
    ret
index        endp

add_code    proc    near
    mov    bx,free_code        ;Get code to use
    push    ds            ;point to hash table
    mov    ds,hash_seg
    cmp    di,0            ;First use of this prefix?
    je    ac1            ;equal means yes
    mov    [si].next,bx        ;point last use to new entry
    jmp    short ac2
ac1:    mov    [si].first,bx        ;Point first use to new entry
ac2:    cmp    bx,maxmax        ;Have we reached code limit?
    je    ac3            ;equal means yes, just return
    call    index            ;get address of new entry
    mov    [si].first,-1        ;initialize pointers
    mov    [si].next,-1
    mov    [si].char,al        ;save suffix char
    inc    es:free_code        ;adjust next code
ac3:    pop    ds            ;restore seg reg
    ret
add_code    endp

code    ends

    end    start